浙江大学2015-16春夏《高级数据结构与算法分析》期中模拟练习

开始时间2016/01/01 08:00:00

结束时间2038/01/18 08:00:00

答题时长60分钟

考生

得分97

总分100

判断题得分：33总分：36

R1-1

When measuring the relevancy of the answer set, if the precision is high but the recall is low, it means that most of the relevant documents are retrieved, but too many irrelevant documents are returned as well.

(3分)

评测结果

答案正确（3 分）

R1-2

For any node in an AVL tree, the height of the left subtree must be greater than that of the right subtree.

(3分)

评测结果

答案正确（3 分）

R1-3

If a problem can be solved by dynamic programming, it must be solved in polynomial time.

(3分)

评测结果

答案正确（3 分）

R1-4

All the languages can be decided by a non-deterministic machine.

(3分)

评测结果

答案正确（3 分）

R1-5

For one operation, if its amortized time bound is $O(logN)$ , then its worst-case time bound must be $O(logN)$ .

(3分)

评测结果

答案正确（3 分）

R1-6

Word stemming is to eliminate the commonly used words from the original documents.

(3分)

评测结果

答案正确（3 分）

R1-7

In a red-black tree, the number of internal nodes in the subtree rooted at $x$ is no more than $2^{bh(x)}-1$ where $bh(x)$ is the black-height of $x$ .

(3分)

评测结果

答案正确（3 分）

R1-8

The right path of a skew heap can be arbitrarily long.

(3分)

评测结果

答案正确（3 分）

R1-9

For any node in an AVL tree, the left and right subtrees must have the same height.

(3分)

评测结果

答案正确（3 分）

R1-10

For one operation, if its average time bound is $O(logN)$ , then its amortized time bound must be $O(logN)$ .

(3分)

评测结果

答案正确（3 分）

R1-11

In a B+ tree, leaves and nonleaf nodes have some key values in common.

(3分)

评测结果

答案正确（3 分）

R1-12

Given that problem A is NP-complete. If problem B is in NP and can be polynomially reduced to problem A, then problem B is NP-complete.

(3分)

评测结果

答案错误（0 分）

单选题得分：52总分：52

R2-1

Which one of the following statements is TRUE?

(4分)

With the same operations, the resulting skew heap is always more balanced than the leftist heap

For leftist heaps and skew heaps, the worst-case running time of a single insertion are both $O(N)$

None of the above is true

The relationship of skew heaps to leftist heaps is analogous to the relation between splay trees and AVL trees

评测结果

答案正确（4 分）

R2-2

Insert {3, 9, 6, 7, 1, 4, 8, 10} into an initially empty 2-3 tree (with splitting), and then delete 7. Which one of the following statements is FALSE about the resulting tree?

(5分)

there are 4 leaf nodes

the first key stored in the root is 4

9 and 8 are in the same node

the parent of the node containing 6 has 3 children

评测结果

答案正确（5 分）

R2-3

Delete the minimum number from the given binomial queue in the following figure. Which one of the following statements is FALSE?

(5分)

11 is the root of a binomial tree

23 is not the root of any resulting binomial tree

there are three binomial trees after deletion, which are $B_0$ , $B_1$ and $B_4$

29 and 23 are both children of 4

评测结果

答案正确（5 分）

R2-4

If the depth of an AVL tree is 5 (the depth of an empty tree is defined to be 0), then the minimum possible number of nodes in this tree is:

(5分)

评测结果

答案正确（5 分）

R2-5

When solving a problem with input size $N$ by divide and conquer, if at each stage the problem is divided into 4 sub-problems of equal size $N/5$ , and the conquer step takes $O(log N)$ to form the solution from the sub-solutions, then the overall time complexity is:

(5分)

$O(log N)$

$O(log^2 N)$

$O(N)$

$O(N^{log 4/log 5})$

评测结果

答案正确（5 分）

R2-6

Starting from the red-black tree given in the figure, after successively inserting the keys {83, 75, 19}, which one of the following statements is FALSE?

(4分)

75 and 99 are siblings, and they are both black

19 is the deepest red node

there are two red nodes

75 is the parent of 83

评测结果

答案正确（4 分）

R2-7

Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?

(4分)

the null path length of 7 is the same as that of 12

37 is the left child of 7

the depths of 24 and 8 are the same

6 is the root with 7 being its right child

评测结果

答案正确（4 分）

R2-8

We can perform BuildHeap for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. Which one of the following statements is FALSE?

(5分)

the time complexity $T(N) = O(\frac{N}{2}log 2^0 + \frac{N}{2^2}log 2^1 + \frac{N}{2^3}log 2^2 + \cdots + \frac{N}{2^K}log 2^{K-1})$ for some integer $K$ so that $N=2^K$

the worst case is when $N=2^K$ for some integer $K$

the worst case time complexity of this algorithm is $\Theta (NlogN)$

in the $k$ -th run, $\lceil N/2^k \rceil$ leftist heaps are formed, each contains $2^k$ nodes

评测结果

答案正确（5 分）

R2-9

A queue can be implemented by using two stacks $S_A$ and $S_B$ as follows:

To enqueue $x$ , we push $x$ onto $S_A$ .
To dequeue from the queue, we pop and return the top item from $S_B$ . However, if $S_B$ is empty, we first fill it (and empty $S_A$ ) by popping the top item from $S_A$ , pushing this item onto $S_B$ , and repeat until $S_A$ is empty.

Assuming that push and pop operations take $O(1)$ worst-case time, please select a potential function $\phi$ which can help us prove that enqueue and dequeue operations take $O(1)$ amortized time (when starting from an empty queue).

(6分)

$\phi = 2|S_A|$

$\phi = 2|S_B|$

$\phi = |S_A|$

$\phi = |S_B|$

评测结果

答案正确（6 分）

R2-10

Rod-cutting Problem: Given a rod of total length $N$ inches and a table of selling prices $P_L$ for lengths $L = 1, 2, \cdots , M$ . You are asked to find the maximum revenue $R_N$ obtainable by cutting up the rod and selling the pieces. For example, based on the following table of prices, if we are to sell an 8-inch rod, the optimal solution is to cut it into two pieces of lengths 2 and 6, which produces revenue $R_8 = P_2 +P_6 = 5+17 = 22$ . And if we are to sell a 3-inch rod, the best way is not to cut it at all.

Length $L$	1	2	3	4	5	6	7	8	9	10
Price $P_L$	1	5	8	9	10	17	17	20	23	28

Which one of the following statements is FALSE?

(5分)

If $N\le M$ , we have $R_N = \max \lbrace P_N , \max_{1\le i < N} \lbrace R_i + R_{N-i} \rbrace \rbrace$

This problem can be solved by dynamic programming

If $N>M$ , we have $R_N = \max_{1\le i < N} \lbrace R_i + R_{N-M} \rbrace$

The time complexity of this algorithm is $O(N^2)$

评测结果

答案正确（5 分）

R2-11

For the result of accessing 5 in the splay tree in the following figure, besides saying that 5 must be the root, which one of the following statements is also TRUE?

(4分)

6 and 10 are siblings

6 is a leaf node

2 and 10 are siblings

4 and 10 are siblings

评测结果

答案正确（4 分）

程序填空题得分：12总分：12

R5-1

The function RL_Rotation is to do right-left rotation to the trouble-finder tree node T in an AVL tree.

typedef struct TNode *Tree;
struct TNode {
    int key, h;
    Tree left, right;
};

Tree RL_Rotation( Tree T )
{
    Tree K1, K2;

    K1 = T->right;
    K2 = K1->left;
    K1->left = (4分);
    T->right = (4分);
    K2->right = K1;
    (4分);
    /* Update the heights */
    K1->h = maxh(Height(K1->left), Height(K1->right)) + 1;
    T->h = maxh(Height(T->left), Height(T->right)) + 1;
    K2->h = maxh(K1->h, T->h) + 1;

    return K2;
}

评测结果

答案正确（12 分）

测试点得分

序号	结果	得分
0	答案正确	4
1	答案正确	4
2	答案正确	4